Back to course home
0% completed
Vote For New Content
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Minimizing Array After Replacing Pairs With Their Product (medium)
Problem Statement
You are given an array containing integers nums and an integer value k. You can perform the below operation on the array elements for multiple times:
- Pick two adjacent elements,
xandy, fromnumsand replace them with a single element equal to their product,x*y, but only ifx*yis less than or equal tok.
Return the minimum possible length of nums after performing multiple operations.
Examples
-
Example 1:
- Input:
nums = [2, 3, 4, 5], k = 10 - Expected Output:
3 - Justification: We can replace 2 and 3 with their product 6 (
[6, 4, 5]). No further operations can be performed since all adjacent products will exceedk. Hence, the minimum length is3.
- Input:
-
Example 2:
- Input:
nums = [1, 2, 2, 3], k = 5 - Expected Output:
2 - Justification: First, replace 2 and 2 with 4 (
[1, 4, 3]), then replace 1 and 4 with 4 ([4, 3]). No more operations can be performed, resulting in a minimum length of2.
- Input:
-
Example 3:
- Input:
nums = [10, 5, 2, 3, 4, 2, 20, 1], k = 50 - Expected Output:
3 - Justification: First, replace 10 and 5 with 50 (
[50, 2, 3, 4, 2, 20, 1]), then replace 2, 3, 4 and 2 with 48 ([50, 48, 20, 1]), and then replace 20 and 1 with 20 ([50, 48, 20]). No more operations can be performed, resulting in a minimum length of3.
- Input:
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Furthest Building You Can Reach
Solution: Minimizing Array After Replacing Pairs With Their Product
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself